<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="en">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="algorithm," />










<meta name="description" content="题目：一个栈的入栈序列是A、B、C、D、E，则栈的不可能的输出序列() A、EDCBA       B、DECBA     C、DCEAB     D、ABCDE 题目从手工操作方面比较容易理解，需要借用一个辅助栈，先理一遍思路： 先看B答案： (0)实始态 入栈序列是ABCDE i出栈序列是CDBEA j栈：|- 一开始有i,j两个下标指向入栈序和出栈序，我们需要C最先出栈，那么就应该让C处于当">
<meta property="og:type" content="article">
<meta property="og:title" content="卡特兰数">
<meta property="og:url" content="http://yoursite.com/2020/07/17/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/index.html">
<meta property="og:site_name" content="LinRaise&#39;s Blog">
<meta property="og:description" content="题目：一个栈的入栈序列是A、B、C、D、E，则栈的不可能的输出序列() A、EDCBA       B、DECBA     C、DCEAB     D、ABCDE 题目从手工操作方面比较容易理解，需要借用一个辅助栈，先理一遍思路： 先看B答案： (0)实始态 入栈序列是ABCDE i出栈序列是CDBEA j栈：|- 一开始有i,j两个下标指向入栈序和出栈序，我们需要C最先出栈，那么就应该让C处于当">
<meta property="og:locale" content="en_US">
<meta property="og:image" content="http://yoursite.com/2020/07/17/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/SouthEast">
<meta property="og:image" content="http://yoursite.com/2020/07/17/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/SouthEast-2">
<meta property="article:published_time" content="2020-07-17T12:12:18.000Z">
<meta property="article:modified_time" content="2020-07-17T12:12:18.000Z">
<meta property="article:author" content="LinRaise">
<meta property="article:tag" content="algorithm">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://yoursite.com/2020/07/17/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/SouthEast">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"right","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: 'Author'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://yoursite.com/2020/07/17/卡特兰数/"/>





  <title>卡特兰数 | LinRaise's Blog</title>
  








<meta name="generator" content="Hexo 4.2.1"></head>

<body itemscope itemtype="http://schema.org/WebPage" lang="en">

  
  
    
  

  <div class="container sidebar-position-right page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">LinRaise's Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle"></p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-question-circle"></i> <br />
            
            Home
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-question-circle"></i> <br />
            
            About
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-question-circle"></i> <br />
            
            Tags
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-question-circle"></i> <br />
            
            Categories
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-question-circle"></i> <br />
            
            Archives
          </a>
        </li>
      

      
        <li class="menu-item menu-item-search">
          
            <a href="javascript:;" class="popup-trigger">
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br />
            
            Search
          </a>
        </li>
      
    </ul>
  

  
    <div class="site-search">
      
  <div class="popup search-popup local-search-popup">
  <div class="local-search-header clearfix">
    <span class="search-icon">
      <i class="fa fa-search"></i>
    </span>
    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
    <div class="local-search-input-wrapper">
      <input autocomplete="off"
             placeholder="Searching..." spellcheck="false"
             type="text" id="local-search-input">
    </div>
  </div>
  <div id="local-search-result"></div>
</div>



    </div>
  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/07/17/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="LinRaise">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="LinRaise's Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">卡特兰数</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2020-07-17T12:12:18+00:00">
                2020-07-17
              </time>
            

            
              <span class="post-meta-divider">|</span>
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-check-o"></i>
              </span>
              
                <span class="post-meta-item-text">Post modified&#58;</span>
              
              <time title="Post modified" itemprop="dateModified" datetime="2020-07-17T12:12:18+00:00">
                2020-07-17
              </time>
            
          </span>

          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>题目：一个栈的入栈序列是A、B、C、D、E，则栈的不可能的输出序列()</p>
<p>A、EDCBA       B、DECBA     <strong>C、DCEAB</strong>     D、ABCDE</p>
<p>题目从手工操作方面比较容易理解，需要借用一个辅助栈，先理一遍思路：</p>
<p>先看B答案：</p>
<p>(0)实始态</p>
<p>入栈序列是ABCDE</p>
<pre><code>i</code></pre><p>出栈序列是CDBEA</p>
<pre><code>j</code></pre><p>栈：|-</p>
<p>一开始有i,j两个下标指向入栈序和出栈序，我们需要C最先出栈，那么就应该让C处于当前栈顶的位置。</p>
<p>因此，需要将ABC入栈</p>
<p>（1）第一步</p>
<p>入栈序列是ABCDE</p>
<pre><code>i</code></pre><p>出栈序列是CDBEA</p>
<pre><code>j</code></pre><p>栈：|-ABC</p>
<p>栈顶为C,出栈序列的j位置为C,刚好可以匹配，因此j后移一位，从栈中弹出栈顶元素</p>
<p>（2）第二步</p>
<p>入栈序列是ABCDE</p>
<pre><code>i</code></pre><p>出栈序列是CDBEA</p>
<pre><code>j</code></pre><p>栈：|-AB</p>
<p>栈顶为B,出栈序列的j位置D,并不匹配，那么需要想办法使得栈顶元素为D.这时可以使入栈序列的i位置的字符继续进栈，期望使得栈顶元素为D。</p>
<p>（3）第三步</p>
<p>入栈序列是ABCDE</p>
<pre><code>i</code></pre><p>出栈序列是CDBEA</p>
<pre><code>j</code></pre><p>栈：|-ABD</p>
<p>栈顶为D,出栈序列的j位置为D,刚好可以匹配，因此j后移一位，从栈中弹出栈顶元素.</p>
<p>（4）第四步</p>
<p>入栈序列是ABCDE</p>
<pre><code>i</code></pre><p>出栈序列是CDBEA</p>
<pre><code>j</code></pre><p>栈：|-AB</p>
<p>栈顶为B,而出栈序列读头j下也是B,可以匹配，因此j后移一位，从栈中弹出栈顶元素。</p>
<p>（4）第四步</p>
<p>入栈序列是ABCDE</p>
<pre><code>i</code></pre><p>出栈序列是CDBEA</p>
<pre><code>j</code></pre><p>栈：|-A</p>
<p>栈顶为A,而出栈序列读头j下是E，不匹配，入栈序列的i位置的字符继续进栈。</p>
<p>（4）第五步</p>
<p>入栈序列是ABCDE</p>
<pre><code>i</code></pre><p>出栈序列是CDBEA</p>
<pre><code>j</code></pre><p>栈：|-AE</p>
<p>栈顶为E,而出栈序列读头j下也是E,可以匹配，因此j后移一位，从栈中弹出栈顶元素。</p>
<p>（4）第六步</p>
<p>入栈序列是ABCDE</p>
<pre><code>i</code></pre><p>出栈序列是CDBEA</p>
<pre><code>j</code></pre><p>栈：|-A</p>
<p>栈顶为A,而出栈序列读头j下是A，可以匹配，因此j后移一位，从栈中弹出栈顶元素。</p>
<p>入栈序列是ABCDE</p>
<pre><code>i</code></pre><p>出栈序列是CDBEA</p>
<pre><code>j</code></pre><p>栈：|-</p>
<p>匹配完成！</p>
<p>总结上面匹配过程的规律：</p>
<p>1.如果读头j能够从开头遍历到末尾，这说明可以成功匹配。</p>
<p>2.当栈顶元素和读头j下的元素相同时，匹配（弹出栈顶元素并且++j）</p>
<p>3.当栈顶元素和读头j下的元素不同时，失配，则入栈序列继续压栈，直至栈顶元素与读头j下元素匹配为止。</p>
<p>4.如果入栈序列一直压栈至最末尾尚未使得栈顶元素等于读头j元素时，说明出栈序列不能和入栈序列匹配。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;iostream&gt;</span><br><span class="line">#include&lt;stack&gt;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">bool isPopStack(char* pPushStack,char* pPopStack)</span><br><span class="line">&#123;</span><br><span class="line">	if( !pPushStack || !pPopStack ||strlen(pPushStack) !&#x3D;strlen(pPopStack))&#x2F;&#x2F;异常处理</span><br><span class="line">		return false;</span><br><span class="line">	stack&lt;char&gt; st;</span><br><span class="line">	while(*pPopStack !&#x3D; &#39;\0&#39;)</span><br><span class="line">	&#123;</span><br><span class="line">		&#x2F;&#x2F;如果前者成立，后者不会被判断，因此不会出现st为空却求st.top()的情况</span><br><span class="line">		while(st.empty() || st.top() !&#x3D; *pPopStack)</span><br><span class="line">		&#123;</span><br><span class="line">			if(*pPushStack &#x3D;&#x3D;&#39;\0&#39;)&#x2F;&#x2F;所有元素都已压栈还是找不到读头j下的元素说明序列不匹配</span><br><span class="line">				return false;</span><br><span class="line">			st.push(*pPushStack);</span><br><span class="line">			++pPushStack;</span><br><span class="line">		&#125;</span><br><span class="line">		&#x2F;&#x2F;!st.empty() &amp;&amp; st.top() &#x3D;&#x3D;*pPopStack</span><br><span class="line">		st.pop();</span><br><span class="line">		++pPopStack;</span><br><span class="line">	&#125;</span><br><span class="line">	return true;</span><br><span class="line">&#125;</span><br><span class="line">void main()</span><br><span class="line">&#123;</span><br><span class="line">	char pPushStack[]&#x3D;&quot;ABCDE&quot;;</span><br><span class="line">	char pPopStack[]&#x3D;&quot;CDBEA&quot;;</span><br><span class="line">	cout&lt;&lt;&quot;pPopStack是否是pPushStack的弹栈序列? (1 or 0) :&quot;</span><br><span class="line">		&lt;&lt;isPopStack(pPushStack,pPopStack)&lt;&lt;endl;</span><br><span class="line">	&#x2F;&#x2F;A、EDCBA       B、DECBA     C、DCEAB     D、ABCDE</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>卡特兰数经典应用(腾讯面试题)：有6个同学去图书馆借还书，书名是《算法导论》。馆中已经没有《算法导论》的存书了。有3个同学是去还书的，有3个同学是去借书的。现在请问，6位同学有多少种借还书的顺序方案可以保证去借书的同学都能借到《算法导论》？</p>
<p>解释：抽象化题目，同学可以用1,2,3,4,5,6表示．还书可以用压栈表示，借书可以用弹栈表示，借还书方案可以表示为弹栈的所有方式．</p>
<p>因此这是另外一种问法：</p>
<p>一个栈的进栈序列为1，2，3，…，n，有多少种不同的出栈序列?</p>
<p>分析：对于每一个数来说，必须进栈一次，出栈一次．我们把进栈设为1，出栈设为-1。n个数的进栈出栈顺序可以组成2n位组合序列a1,a2,a3,a4……．</p>
<p>假设n=4(等待入栈的顺序是1，2，3，4)</p>
<p>则其中一个进出栈顺序可以表示为1 , 1 , 1 , 1,-1,-1,-1,-1.即“进进进进出出出出”。这是一种进出栈的方式。</p>
<p>2n位二进制数序列需要保证两个条件成立：</p>
<p>1 .由n个1和n个-1组成（有多少个数进栈就应该有多少个数出栈）。</p>
<p>2.从左往右扫描到的每一位k，在k（包括k）之前1的总数必须大于或等于-1的总数（即进栈的个数要比出栈的个数多，不允许出现栈空却要出栈的情况）</p>
<p>在2n位二进制数中填入n个1的方案数为,不填1的其余n位自动填-1。从中减去不符合要求（由左而右扫描，-1的总数大于1的总数）的方案数即为所求。</p>
<p>接下来的任务就是找不符合要求的方案数了，这是难点。对于一个不合要求的序列，我们假设有一个最小的k令a1+a2+a3+……+ak&lt;0。由于这里k是最小的，所以必有a1+a2+a3+……+ak＝-1。并且k是奇数，(注：因为k个(1,-1)相加结果是-1,必定是-1比1多1个.若1有m个,则-1有m+1个,总数=2m+1)。</p>
<p>不妨设k=2m+1,则a1,a2…ak中有m+1个-1和m个1.</p>
<p>此后的2n-(2m+1)位有n-(m+1)个-1和n-m个1。如果将后2n-(2m+1)位的0和1置换，使之变成n-(m+1)个1和n-m个－1。结果有n+1个-1和n-1个1。即一个不合要求的序列对应一个由n+1个0和n-1个1组成的排列。</p>
<p>反过来，任何一个由n+1个0和n-1个1组成的2n位二进制数，由于-1的个数多2个，2n为偶数，故必在某一个奇数位上出现-1的累计数超过1的累计数。（不合要求的序列）同样在后面部分-1和1互换，使之成为由n个-1和n个1组成的2n位数，即n+1个-1和n-1个1组成的2n位数必对应一个不符合要求的序列。</p>
<p>因而不合要求的2n位数与n+1个0，n－1个1组成的排列一一对应。</p>
<p>显然，不符合要求的方案数为c(2n,n+1)。由此得出输出序列的总数目=-c(2n,n+1)=/(n+1)=h(n+1)。</p>
<p>小结：</p>
<ol>
<li><p>对于n个元素的进出栈顺序，由于每个元素都各进出一次，我们可以用2n位表示n个元素的进出栈序列。</p>
</li>
<li><p>进栈记为1,出栈记为-1，则2n位有n位为1,n位为-1,总共的组合数有</p>
</li>
<li><p>在总共的组合序中有一部分序列不满足要求（栈已经为空却硬要出栈），因此我们需要减去这一部分不合要求的序列数。</p>
</li>
</ol>
<p>a1,a2,a3,a4……..a2n中假设有最小的k满足a1,a2,a3,………..ak&lt;0(不合要求的序列)，因k已最小，ak=-1,a1+a2+…+ak-1=0,所以k为奇数k=2m+1,前边有m+1个-1，m个1。将此后n-k个数-1，1置换,则后面有n-m-1个1,n-m个-1.前后总共有n-1个1,n+1个-1.因此，每一个不合要求的序列都和有n-1个1,n+1个-1的2n位二进制数对应</p>
<p>继续证明反之也成立。一个n-1个1,n+1个-1的2n位二进制数是否与和一个不合要求的序列（n个1,n个-1）相对应？由于-1比1多2个，整个序列加起来为-2，则必然存在一个最小k使得某一部分序列a1+a2+a3++..+ak&lt;0(实质上等于-1，并且k不是末尾，否则=-2)，同理k为奇数。则将k后面的数-1,1置换，则总共会有n个1和n个-1。则每一个n-1个1，n+1个-1的2n位二进制数都与一个不合要求的序列(a1+a2+..ak&lt;0且-1,1个数都为n)对应，故证。</p>
<p><img src="/2020/07/17/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/SouthEast" alt="img"></p>
<p>最后给出卡特兰公式:H(n)=-C(2n,n+1)</p>
<p>一个栈的进栈序列为1，2，3，…，n，有多少种不同的出栈序列?</p>
<p>重新回到这道题上面来，下面的程序基于卡特兰公式的思路。</p>
<p>1,2,3……n可以用2n位表示入栈出栈序列。在2n位中填入n个1，有C2n,n种办法，可以联想到字符串组合的程序</p>
<p>对于当前索引index,如果index选择填1，则只需要在余下的2n-1中填入n-1个1，如果index不选择填入1，则需要在余下的2n-1中填入n个1.可以用递归实现。</p>
<p>再写一个子函数判断这是否可以组成弹栈序列，只需要一直累加和&gt;=0则表示可组成，否则不是一个弹栈序列。</p>
<p>再写一个输出函数即可。时间效率上是指数级的。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;iostream&gt;</span><br><span class="line">#include&lt;vector&gt;</span><br><span class="line">#include&lt;stack&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">&#x2F;***********************************************</span><br><span class="line">判断字符串组合是否可以构成一个压栈弹栈序列</span><br><span class="line">************************************************&#x2F;</span><br><span class="line">bool IsPopQueue(vector&lt;int&gt;&amp; result )</span><br><span class="line">&#123;</span><br><span class="line">	int Sum &#x3D; 0 ;</span><br><span class="line">	vector&lt;int&gt;::iterator iter &#x3D; result.begin();</span><br><span class="line">	for(; iter &lt; result.end(); ++ iter)</span><br><span class="line">	&#123;</span><br><span class="line">		Sum +&#x3D;*iter;</span><br><span class="line">		if(Sum &lt; 0) &#x2F;&#x2F;a1+a2+a3+..+ak &lt; 0则不符合要求</span><br><span class="line">			return false;</span><br><span class="line">	&#125;</span><br><span class="line">	return true;</span><br><span class="line">&#125;</span><br><span class="line">&#x2F;&#x2F;输出弹栈序列</span><br><span class="line">void PrintPopQueue(vector&lt;int&gt;&amp; result )</span><br><span class="line">&#123;</span><br><span class="line">	stack&lt;int&gt; Stack; </span><br><span class="line">	int Index&#x3D;1;</span><br><span class="line">	for(int i &#x3D; 0 ; i &lt; result.size(); ++ i)</span><br><span class="line">	&#123;</span><br><span class="line">		if( result[i] &#x3D;&#x3D; 1)</span><br><span class="line">			Stack.push(Index++);</span><br><span class="line">		else</span><br><span class="line">		&#123;</span><br><span class="line">			cout&lt;&lt;&#39; &#39;&lt;&lt;Stack.top();</span><br><span class="line">			Stack.pop();</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line">&#x2F;***********************************************</span><br><span class="line">字符串组合</span><br><span class="line">************************************************&#x2F;</span><br><span class="line">void Combination(int Index, int number, vector&lt;int&gt;&amp; result)</span><br><span class="line">&#123;</span><br><span class="line">	static int count&#x3D;0;</span><br><span class="line">	if(number &#x3D;&#x3D; 0)</span><br><span class="line">	&#123;</span><br><span class="line">		if(IsPopQueue(result))</span><br><span class="line">		&#123;</span><br><span class="line">			++count;</span><br><span class="line">			vector&lt;int&gt;::iterator iter &#x3D; result.begin();</span><br><span class="line">			for(; iter &lt; result.end(); ++ iter)</span><br><span class="line">				printf(&quot;%d &quot;, *iter);</span><br><span class="line">			PrintPopQueue(result);</span><br><span class="line">			printf(&quot;  %d \n&quot;,count);</span><br><span class="line">		&#125;</span><br><span class="line">		return;</span><br><span class="line">	&#125;</span><br><span class="line">	if(Index &lt; 0)</span><br><span class="line">	    return;</span><br><span class="line">	result[Index] &#x3D; 1 ;</span><br><span class="line">	Combination( Index-1 , number - 1, result);</span><br><span class="line">	result[Index] &#x3D; -1 ;</span><br><span class="line">	Combination( Index-1 , number, result);</span><br><span class="line">&#125;</span><br><span class="line">void main()</span><br><span class="line">&#123;</span><br><span class="line">	vector&lt;int&gt; Result(8,-1);</span><br><span class="line">	Combination(7,4,Result);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>另外一种思考方式。根据栈中的状态和Vector中的状态，可以有两种先择，一种选择是将Vector中的值压到栈中去，Vector中的索引后移一位，继续递归下降调用。另一种选择是将Stack顶元素弹到Result中保存起来，继续递归下降调用。具体实现见代码。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;iostream&gt;</span><br><span class="line">#include&lt;stack&gt;</span><br><span class="line">#include&lt;vector&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">void Combination(stack&lt;int&gt;&amp; Stack,vector&lt;int&gt;&amp; Vec,int Index,vector&lt;int&gt;&amp; Result)</span><br><span class="line">&#123;</span><br><span class="line">	if(Vec.size() &lt; 1)</span><br><span class="line">		return ;</span><br><span class="line">	&#x2F;&#x2F;如果栈空且Index遍历到了末尾，这说明，Result中已经保存了Vec中的所有数</span><br><span class="line">	if(Stack.empty() &amp;&amp; Vec.size() &#x3D;&#x3D; Index)</span><br><span class="line">	&#123;</span><br><span class="line">		for(int i&#x3D;0;i&lt;Result.size();++i)</span><br><span class="line">			cout&lt;&lt;Result[i]&lt;&lt;&quot; &quot;;</span><br><span class="line">		cout&lt;&lt;endl;</span><br><span class="line">		return ;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	&#x2F;&#x2F;!Stack.empty() || Vec.size() !&#x3D;Index</span><br><span class="line">	if(!Stack.empty())&#x2F;&#x2F;分两条分支，一条为将栈中值弹到Result中</span><br><span class="line">	&#123;</span><br><span class="line">		int Temp&#x3D;Stack.top();</span><br><span class="line">		Result.push_back(Temp);</span><br><span class="line">		Stack.pop();</span><br><span class="line">	 </span><br><span class="line">		Combination(Stack,Vec,Index,Result);</span><br><span class="line">	 </span><br><span class="line">		Stack.push(Temp);</span><br><span class="line">		Result.pop_back();</span><br><span class="line">	&#125;	</span><br><span class="line">	&#x2F;&#x2F;Stack.empty() &amp;&amp; Vec.size() !&#x3D;Index</span><br><span class="line">	if(Vec.size() !&#x3D; Index)</span><br><span class="line">	&#123;</span><br><span class="line">		Stack.push(Vec[Index]);</span><br><span class="line">		&#x2F;&#x2F;分两条分支，一条为将Vec[Index]中的值压进栈</span><br><span class="line">		Combination(Stack,Vec,Index+1,Result);</span><br><span class="line">		Stack.pop();</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()</span><br><span class="line">&#123;</span><br><span class="line">	vector&lt;int&gt; Vec;</span><br><span class="line">	Vec.push_back(1);</span><br><span class="line">	Vec.push_back(2);</span><br><span class="line">	Vec.push_back(3);</span><br><span class="line">	Vec.push_back(4);</span><br><span class="line">	stack&lt;int&gt; Stack;</span><br><span class="line">	vector&lt;int&gt; Result;</span><br><span class="line">	Combination(Stack,Vec,0,Result);</span><br><span class="line">	return 0 ;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>或者</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br></pre></td><td class="code"><pre><span class="line">#include &lt;iostream&gt;</span><br><span class="line">#include &lt;vector&gt;</span><br><span class="line">#include &lt;iomanip&gt;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">void Combination(int A[], int Index, int ALen, vector&lt;int&gt;&amp; Stack, vector&lt;int&gt;&amp; Queue)</span><br><span class="line">&#123;</span><br><span class="line">	static int count &#x3D; 0;</span><br><span class="line">	if (Index &#x3D;&#x3D; ALen)</span><br><span class="line">	&#123;</span><br><span class="line">		cout &lt;&lt; ++count &lt;&lt; &quot;: &quot;;</span><br><span class="line">		for (unsigned int k &#x3D; 0; k &lt; Queue.size(); k++)</span><br><span class="line">		&#123;</span><br><span class="line">			cout &lt;&lt; setw(5) &lt;&lt; Queue[k];</span><br><span class="line">		&#125;</span><br><span class="line">		for (int k &#x3D; Stack.size() - 1; k &gt;&#x3D; 0; k--)</span><br><span class="line">		&#123;</span><br><span class="line">			cout &lt;&lt; setw(5) &lt;&lt; Stack[k];</span><br><span class="line">		&#125;</span><br><span class="line">		cout &lt;&lt; endl;</span><br><span class="line">		return;</span><br><span class="line">	&#125;</span><br><span class="line">	&#x2F;&#x2F;Index !&#x3D;ALen</span><br><span class="line">	Stack.push_back(A[Index]); </span><br><span class="line">	Combination(A, Index + 1, ALen, Stack, Queue);\</span><br><span class="line">	Stack.pop_back(); </span><br><span class="line">	if (!Stack.empty())</span><br><span class="line">	&#123;</span><br><span class="line">		Queue.push_back(Stack.back());</span><br><span class="line">		Stack.pop_back();</span><br><span class="line">		Combination(A, Index, ALen, Stack, Queue); </span><br><span class="line">		Stack.push_back(Queue[Queue.size() - 1]);	</span><br><span class="line">		Queue.pop_back();</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()</span><br><span class="line">&#123;</span><br><span class="line">	int A[] &#x3D; &#123;1, 2, 3, 4&#125;;</span><br><span class="line">	vector&lt;int&gt; Stack;</span><br><span class="line">	vector&lt;int&gt; Queue;</span><br><span class="line">	Combination(A, 0, sizeof(A) &#x2F; sizeof(int),	Stack, Queue);</span><br><span class="line">	return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>实训：<a href="http://acm.hdu.edu.cn/showproblem.php?pid=1515" target="_blank" rel="noopener">http://acm.hdu.edu.cn/showproblem.php?pid=1515</a></p>
<p>Problem Description</p>
<p>How can anagrams result from sequences of stack operations? There are two sequences of stack operators which can convert TROT to TORT: </p>
<p> [</p>
<p>i i i i o o o o</p>
<p>i o i i o o i o</p>
<p>]</p>
<p>where i stands for Push and o stands for Pop. Your program should, given pairs of words produce sequences of stack operations which convert the first word to the second.</p>
<p>A stack is a data storage and retrieval structure permitting two operations: </p>
<p>Push - to insert an item and</p>
<p>Pop - to retrieve the most recently pushed item </p>
<p>We will use the symbol i (in) for push and o (out) for pop operations for an initially empty stack of characters. Given an input word, some sequences of push and pop operations are valid in that every character of the word is both pushed and popped, and furthermore, no attempt is ever made to pop the empty stack. For example, if the word FOO is input, then the sequence: </p>
<p>i i o i o o is valid, but </p>
<p>i i o is not (it’s too short), neither is </p>
<p>i i o o o i (there’s an illegal pop of an empty stack) </p>
<p>Valid sequences yield rearrangements of the letters in an input word. For example, the input word FOO and the sequence i i o i o o produce the anagram OOF. So also would the sequence i i i o o o. You are to write a program to input pairs of words and output all the valid sequences of i and o which will produce the second member of each pair from the first.</p>
<p>题目很多英文，看了半小时才明白题目要求做什么，英语水平不好很吃亏．题目大致要求是：给出两个字串str1,str2,利用一个栈，找出有多少种方法(即进栈出栈操作．)可以从str1得到str2.先看看状态转移有哪些．</p>
<p>(１)如果str1和str2包含有不同的字符，或者长度不一，或者相同字符数目不同，则我们可以不做任何操作，直接返回false.就是sort(str1),sort(str2),if(str1!=str2) do nothing.</p>
<p>如果通过第(１)步的检测，则开始看状态转移：<strong>(str1中的字符进栈和栈顶元素出栈)</strong></p>
<p><img src="/2020/07/17/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/SouthEast-2" alt="img"></p>
<p>(２)<strong>进栈！</strong>如果str1中当前字符索引index还没有到末尾，即str1还有字符未处理完毕，则str1[index]可以选择进栈．(栈为空，str1[index]可以进栈，栈不空，一样可以进栈，str1[index]!=str2[rIndex],可以进栈，str1[index]==str2[rIndex],可以进栈，stack.top==str2[rIndex]可以进栈，因为虽然当前栈顶元素和str2[rIndex]相等，但是一样可以进栈是因为后续进栈的元素还有可能等于str2[rIndex],stack.top!=str2[rIndex]可以进栈,所以str1[index]的进栈只要str1尚未处理完就可以进行．)</p>
<p>(３)<strong>出栈！</strong>如果栈不为空而且栈顶元素等于str2[rIndex]才可以出栈(表示匹配．)这个很容易理解．</p>
<p>利用(２)(３)的状态转移就可以写出递归函数，<strong>当然因为使用的是全局堆栈，所以，需要记住还原现场</strong>．</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br></pre></td><td class="code"><pre><span class="line">#include &lt;iostream&gt;</span><br><span class="line">#include&lt;string&gt;</span><br><span class="line">#include&lt;stack&gt;</span><br><span class="line">#include &lt;algorithm&gt;</span><br><span class="line">#include &lt;vector&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">string str1,str2;</span><br><span class="line">vector&lt;char&gt; result;</span><br><span class="line">stack&lt;char&gt; st;</span><br><span class="line">void Combination(int index,int rIndex)</span><br><span class="line">&#123;</span><br><span class="line">	if( rIndex &#x3D;&#x3D; str2.length())</span><br><span class="line">	&#123;</span><br><span class="line">		for(int i&#x3D;0;i&lt;result.size();++i)</span><br><span class="line">			cout&lt;&lt;result[i]&lt;&lt;&#39; &#39;;</span><br><span class="line">		cout&lt;&lt;endl;</span><br><span class="line">		return ;</span><br><span class="line">	&#125;</span><br><span class="line">	if( index &lt; str1.length())&#x2F;&#x2F;str1的字符还没有处理完，则可以选择压栈，第2分支</span><br><span class="line">	&#123;</span><br><span class="line">		result.push_back(&#39;i&#39;);</span><br><span class="line">		st.push(str1[index]);&#x2F;&#x2F;2</span><br><span class="line">		Combination(index+1,rIndex);</span><br><span class="line">		st.pop();&#x2F;&#x2F;recover</span><br><span class="line">		result.pop_back();&#x2F;&#x2F;recover</span><br><span class="line">	&#125;</span><br><span class="line">	if( !st.empty() &amp;&amp; st.top() &#x3D;&#x3D;str2[rIndex])&#x2F;&#x2F;栈不为空且栈顶元素等于str2[rIndex]，可以选择弹栈,第2分支</span><br><span class="line">	&#123;</span><br><span class="line">		result.push_back(&#39;o&#39;);</span><br><span class="line">		char temp&#x3D;st.top();</span><br><span class="line">		st.pop();&#x2F;&#x2F;</span><br><span class="line">		Combination(index,rIndex+1);</span><br><span class="line">		result.pop_back();&#x2F;&#x2F;recover </span><br><span class="line">		st.push(temp);&#x2F;&#x2F;recover </span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()</span><br><span class="line">&#123;</span><br><span class="line">	while(cin&gt;&gt;str1&gt;&gt;str2)</span><br><span class="line">	&#123;</span><br><span class="line">		cout&lt;&lt;&#39;[&#39;&lt;&lt;endl;</span><br><span class="line">		if(str2.length()&#x3D;&#x3D;str1.length())</span><br><span class="line">		&#123;</span><br><span class="line">			string t1&#x3D;str1, t2&#x3D;str2;</span><br><span class="line">			sort(t1.begin(), t1.end());</span><br><span class="line">			sort(t2.begin(), t2.end());</span><br><span class="line">			if(t1&#x3D;&#x3D;t2)&#x2F;&#x2F;if the two string have the same char,then go ahead.</span><br><span class="line">			&#123;</span><br><span class="line">				Combination(0,0);</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		cout&lt;&lt;&#39;]&#39;&lt;&lt;endl;</span><br><span class="line">	&#125;</span><br><span class="line">	return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>卡特兰练兵场：HDU2067小兔的棋盘</p>
<p>小兔的棋盘</p>
<p>Problem Description</p>
<p>小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?小兔想了很长时间都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧!</p>
<p>Input</p>
<p>每次输入一个数n(1&lt;=n&lt;=35)，当n等于－1时结束输入。</p>
<p>Output 对于每个输入数据输出路径数，具体格式看Sample。</p>
<p>Sample Input 1</p>
<p>3</p>
<p>12</p>
<p>-1</p>
<p>Sample Output 1 1 2</p>
<p>2 3 10</p>
<p>3 12 416024</p>
<p>解释：</p>
<p>维基百科上卡特兰数可以用两个式子推导Click me~wikipedia。</p>
<p>第一个式子用__int64刚好不溢出，而第二个式子需要用java的大数类来解决，下面给出代码：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line">#include &lt;iostream&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">const int MAX &#x3D; 40;</span><br><span class="line"></span><br><span class="line">&#x2F;&#x2F;http:&#x2F;&#x2F;zh.wikipedia.org&#x2F;wiki&#x2F;%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0</span><br><span class="line"></span><br><span class="line">__int64 Catalan[MAX];</span><br><span class="line"></span><br><span class="line">int main()</span><br><span class="line">&#123;</span><br><span class="line">	Catalan[0] &#x3D; Catalan[1] &#x3D; 1;</span><br><span class="line">	int i,j;</span><br><span class="line">	__int64 sum;</span><br><span class="line">	for (i&#x3D;2; i&lt;MAX; ++i)</span><br><span class="line">	&#123;</span><br><span class="line">		sum &#x3D; 0;</span><br><span class="line">		for (j&#x3D;0; j&lt;i; ++j)</span><br><span class="line">		&#123;</span><br><span class="line">			sum +&#x3D; Catalan[j] * Catalan[i-j-1];</span><br><span class="line">		&#125;</span><br><span class="line">		Catalan[i] &#x3D; sum;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	int t &#x3D; 1,n;</span><br><span class="line">	while( cin &gt;&gt; n &amp;&amp; n!&#x3D;-1 )</span><br><span class="line">	&#123;</span><br><span class="line">		printf(&quot;%d %d %I64d\n&quot;,t++,n,Catalan[n]*2);</span><br><span class="line">	&#125;</span><br><span class="line">	return 0;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;iostream&gt;</span><br><span class="line">#include&lt;cstdio&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">__int64 c[36]&#x3D;&#123;</span><br><span class="line">1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, </span><br><span class="line">2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, </span><br><span class="line">24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, </span><br><span class="line">18367353072152, 69533550916004, 263747951750360, 1002242216651368,</span><br><span class="line"> 3814986502092304, 14544636039226909, 55534064877048198, 212336130412243110,</span><br><span class="line">  812944042149730764, 3116285494907301262  &#125;;</span><br><span class="line">int main()</span><br><span class="line">&#123;</span><br><span class="line">    int n;</span><br><span class="line">    int flag&#x3D;1;</span><br><span class="line">    while(cin&gt;&gt;n&amp;&amp;n!&#x3D;-1)</span><br><span class="line">    &#123;</span><br><span class="line">        printf(&quot;%d %d %I64d\n&quot;,flag++,n,c[n]*2);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    return 0;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>蹩脚的java又要献丑了</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line">import java.io.*;</span><br><span class="line">import java.math.*;</span><br><span class="line">import java.util.*;</span><br><span class="line"></span><br><span class="line">public class Main </span><br><span class="line">&#123;</span><br><span class="line">    public static void main(String[] args) </span><br><span class="line">    &#123;</span><br><span class="line">        Scanner cin &#x3D; new Scanner(System.in);</span><br><span class="line">        Integer N &#x3D; 36, i,t &#x3D; 1;</span><br><span class="line">        BigInteger[] cat &#x3D; new BigInteger[N];</span><br><span class="line"></span><br><span class="line">        cat[0] &#x3D; cat[1] &#x3D; BigInteger.valueOf(1);</span><br><span class="line">        for (i &#x3D; 2; i &lt; N; ++i) </span><br><span class="line">        &#123;</span><br><span class="line">            cat[i] &#x3D; cat[i - 1].multiply(BigInteger.valueOf(i * 4 - 2)).divide(BigInteger.valueOf(i + 1));</span><br><span class="line">        &#125;</span><br><span class="line">     </span><br><span class="line">        while (cin.hasNext()) </span><br><span class="line">        &#123;</span><br><span class="line">            i &#x3D; cin.nextInt();</span><br><span class="line">            if (i &#x3D;&#x3D; -1)</span><br><span class="line">                break;</span><br><span class="line">            System.out.println(t++ + &quot; &quot; + i + &quot; &quot; + cat[i].multiply(BigInteger.valueOf(2)));</span><br><span class="line">        &#125;</span><br><span class="line">     </span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>参考资料：</p>
<p><a href="http://baike.baidu.com/view/2499752.htm" target="_blank" rel="noopener">http://baike.baidu.com/view/2499752.htm</a></p>
<p><a href="http://www.cnblogs.com/muzinian/archive/2012/11/08/2761430.html" target="_blank" rel="noopener">http://www.cnblogs.com/muzinian/archive/2012/11/08/2761430.html</a></p>
<p><a href="http://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0" target="_blank" rel="noopener">http://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0</a></p>

      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/algorithm/" rel="tag"># algorithm</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2020/07/16/%E4%BA%8C%E5%8F%89%E6%A0%91/" rel="next" title="二叉树">
                <i class="fa fa-chevron-left"></i> 二叉树
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2020/07/20/%E6%A0%91%E3%80%81%E6%A3%AE%E6%9E%97%E4%B8%8E%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BD%AC%E6%8D%A2/" rel="prev" title="树、森林与二叉树的转换">
                树、森林与二叉树的转换 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      

      <section class="site-overview-wrap sidebar-panel sidebar-panel-active">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <p class="site-author-name" itemprop="name">LinRaise</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">16</span>
                  <span class="site-state-item-name">posts</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">2</span>
                  <span class="site-state-item-name">categories</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">1</span>
                  <span class="site-state-item-name">tags</span>
                </a>
              </div>
            

          </nav>

          

          

          
          

          
          

          

        </div>
      </section>

      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">LinRaise</span>

  
</div>


  <div class="powered-by">Powered by <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a></div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">Theme &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Gemini</a> v5.1.4</div>




        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.4"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  

  <script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    var isXml = true;
    // Search DB path;
    var search_path = "search.xml";
    if (search_path.length === 0) {
      search_path = "search.xml";
    } else if (/json$/i.test(search_path)) {
      isXml = false;
    }
    var path = "/" + search_path;
    // monitor main search box;

    var onPopupClose = function (e) {
      $('.popup').hide();
      $('#local-search-input').val('');
      $('.search-result-list').remove();
      $('#no-result').remove();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    }

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.search-popup-overlay').click(onPopupClose);
      $('.popup').toggle();
      var $localSearchInput = $('#local-search-input');
      $localSearchInput.attr("autocapitalize", "none");
      $localSearchInput.attr("autocorrect", "off");
      $localSearchInput.focus();
    }

    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';

      // start loading animation
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay">' +
          '<div id="search-loading-icon">' +
          '<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
          '</div>' +
          '</div>')
        .css('overflow', 'hidden');
      $("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');

      $.ajax({
        url: path,
        dataType: isXml ? "xml" : "json",
        async: true,
        success: function(res) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = isXml ? $("entry", res).map(function() {
            return {
              title: $("title", this).text(),
              content: $("content",this).text(),
              url: $("url" , this).text()
            };
          }).get() : res;
          var input = document.getElementById(search_id);
          var resultContent = document.getElementById(content_id);
          var inputEventFunction = function() {
            var searchText = input.value.trim().toLowerCase();
            var keywords = searchText.split(/[\s\-]+/);
            if (keywords.length > 1) {
              keywords.push(searchText);
            }
            var resultItems = [];
            if (searchText.length > 0) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var hitCount = 0;
                var searchTextCount = 0;
                var title = data.title.trim();
                var titleInLowerCase = title.toLowerCase();
                var content = data.content.trim().replace(/<[^>]+>/g,"");
                var contentInLowerCase = content.toLowerCase();
                var articleUrl = decodeURIComponent(data.url);
                var indexOfTitle = [];
                var indexOfContent = [];
                // only match articles with not empty titles
                if(title != '') {
                  keywords.forEach(function(keyword) {
                    function getIndexByWord(word, text, caseSensitive) {
                      var wordLen = word.length;
                      if (wordLen === 0) {
                        return [];
                      }
                      var startPosition = 0, position = [], index = [];
                      if (!caseSensitive) {
                        text = text.toLowerCase();
                        word = word.toLowerCase();
                      }
                      while ((position = text.indexOf(word, startPosition)) > -1) {
                        index.push({position: position, word: word});
                        startPosition = position + wordLen;
                      }
                      return index;
                    }

                    indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
                    indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
                  });
                  if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
                    isMatch = true;
                    hitCount = indexOfTitle.length + indexOfContent.length;
                  }
                }

                // show search results

                if (isMatch) {
                  // sort index by position of keyword

                  [indexOfTitle, indexOfContent].forEach(function (index) {
                    index.sort(function (itemLeft, itemRight) {
                      if (itemRight.position !== itemLeft.position) {
                        return itemRight.position - itemLeft.position;
                      } else {
                        return itemLeft.word.length - itemRight.word.length;
                      }
                    });
                  });

                  // merge hits into slices

                  function mergeIntoSlice(text, start, end, index) {
                    var item = index[index.length - 1];
                    var position = item.position;
                    var word = item.word;
                    var hits = [];
                    var searchTextCountInSlice = 0;
                    while (position + word.length <= end && index.length != 0) {
                      if (word === searchText) {
                        searchTextCountInSlice++;
                      }
                      hits.push({position: position, length: word.length});
                      var wordEnd = position + word.length;

                      // move to next position of hit

                      index.pop();
                      while (index.length != 0) {
                        item = index[index.length - 1];
                        position = item.position;
                        word = item.word;
                        if (wordEnd > position) {
                          index.pop();
                        } else {
                          break;
                        }
                      }
                    }
                    searchTextCount += searchTextCountInSlice;
                    return {
                      hits: hits,
                      start: start,
                      end: end,
                      searchTextCount: searchTextCountInSlice
                    };
                  }

                  var slicesOfTitle = [];
                  if (indexOfTitle.length != 0) {
                    slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
                  }

                  var slicesOfContent = [];
                  while (indexOfContent.length != 0) {
                    var item = indexOfContent[indexOfContent.length - 1];
                    var position = item.position;
                    var word = item.word;
                    // cut out 100 characters
                    var start = position - 20;
                    var end = position + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if (end < position + word.length) {
                      end = position + word.length;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
                  }

                  // sort slices in content by search text's count and hits' count

                  slicesOfContent.sort(function (sliceLeft, sliceRight) {
                    if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
                      return sliceRight.searchTextCount - sliceLeft.searchTextCount;
                    } else if (sliceLeft.hits.length !== sliceRight.hits.length) {
                      return sliceRight.hits.length - sliceLeft.hits.length;
                    } else {
                      return sliceLeft.start - sliceRight.start;
                    }
                  });

                  // select top N slices in content

                  var upperBound = parseInt('1');
                  if (upperBound >= 0) {
                    slicesOfContent = slicesOfContent.slice(0, upperBound);
                  }

                  // highlight title and content

                  function highlightKeyword(text, slice) {
                    var result = '';
                    var prevEnd = slice.start;
                    slice.hits.forEach(function (hit) {
                      result += text.substring(prevEnd, hit.position);
                      var end = hit.position + hit.length;
                      result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
                      prevEnd = end;
                    });
                    result += text.substring(prevEnd, slice.end);
                    return result;
                  }

                  var resultItem = '';

                  if (slicesOfTitle.length != 0) {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
                  } else {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
                  }

                  slicesOfContent.forEach(function (slice) {
                    resultItem += "<a href='" + articleUrl + "'>" +
                      "<p class=\"search-result\">" + highlightKeyword(content, slice) +
                      "...</p>" + "</a>";
                  });

                  resultItem += "</li>";
                  resultItems.push({
                    item: resultItem,
                    searchTextCount: searchTextCount,
                    hitCount: hitCount,
                    id: resultItems.length
                  });
                }
              })
            };
            if (keywords.length === 1 && keywords[0] === "") {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
            } else if (resultItems.length === 0) {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
            } else {
              resultItems.sort(function (resultLeft, resultRight) {
                if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
                  return resultRight.searchTextCount - resultLeft.searchTextCount;
                } else if (resultLeft.hitCount !== resultRight.hitCount) {
                  return resultRight.hitCount - resultLeft.hitCount;
                } else {
                  return resultRight.id - resultLeft.id;
                }
              });
              var searchResultList = '<ul class=\"search-result-list\">';
              resultItems.forEach(function (result) {
                searchResultList += result.item;
              })
              searchResultList += "</ul>";
              resultContent.innerHTML = searchResultList;
            }
          }

          if ('auto' === 'auto') {
            input.addEventListener('input', inputEventFunction);
          } else {
            $('.search-icon').click(inputEventFunction);
            input.addEventListener('keypress', function (event) {
              if (event.keyCode === 13) {
                inputEventFunction();
              }
            });
          }

          // remove loading animation
          $(".local-search-pop-overlay").remove();
          $('body').css('overflow', '');

          proceedsearch();
        }
      });
    }

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched === false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(onPopupClose);
    $('.popup').click(function(e){
      e.stopPropagation();
    });
    $(document).on('keyup', function (event) {
      var shouldDismissSearchPopup = event.which === 27 &&
        $('.search-popup').is(':visible');
      if (shouldDismissSearchPopup) {
        onPopupClose();
      }
    });
  </script>





  

  

  

  
  

  

  

  

</body>
</html>
